Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Binary Tree Paths

Problem Statement

Given the root node of a binary tree, return all unique paths from the root node to the leaf node in any order.

Examples

Example 1:

  • Input: root = [1,2,3,null,null,4,5]
Image
  • Expected Output: ["1->2", "1->3->4", "1->3->5"]
  • Justification: The binary tree has one root-to-leaf path for the left child (1->2) and two for the right child, branching into 4 and 5 respectively.

Example 2:

  • Input: root = [5,3,6,2,4,null,null,1]
Image
  • Expected Output: ["5->3->2->1", "5->3->4", "5->6"]
  • Justification: There are three paths leading to leaf nodes: one through the left subtree down to 1, another through the left subtree to 4, and one path through the right subtree to 6.

Example 3:

  • Input: root = [2,null,3,null,4,null,5]
Image
  • Expected Output: ["2->3->4->5"]
  • Justification: There's only one path from the root to the leaf, cascading down the right children.

Solution

To solve this problem, we will employ a depth-first search (DFS) approach. DFS is particularly well-suited for this task because it allows us to explore each branch of the tree to its fullest extent (down to the leaf nodes) before backtracking. This ensures that we can collect all root-to-leaf paths efficiently. The algorithm works by traversing the tree from the root node, appending the value of each visited node to a path string, and recursively exploring all possible paths down to the leaf nodes. Once a leaf node is reached, the current path string is added to a list of paths. This method is applied recursively to each node's left and right children if they exist. By using DFS, we can guarantee that all paths are explored, and the use of recursion simplifies the traversal logic.

Our approach is effective because it aligns with the natural structure of binary trees, allowing us to leverage their hierarchical nature to efficiently navigate and record paths. DFS ensures that no node is missed and that each path is fully recorded before moving on to the next. This strategy is optimal for this problem because it minimizes unnecessary computations and visits each node exactly once, ensuring all unique root-to-leaf paths are captured.

Step-by-Step Algorithm

  1. Start at the Root: Begin the process with the root node of the binary tree.

  2. Initialize Paths List: Create an empty list to store the paths from the root to each leaf.

  3. Recursive Function - findPaths: Define a recursive function that takes the current node, the path so far (as a string), and the paths list as arguments. This function will be used to explore all possible paths from the root to the leaves.

  4. Base Case: In the recursive function, check if the current node is null. If it is, return immediately, as this path cannot lead to a leaf.

  5. Update Path: Append the current node's value to the path string. If the current node is not null, this means we are on a potential path to a leaf.

  6. Leaf Node Check: Check if the current node is a leaf (i.e., both its left and right children are null). If it is, add the current path to the paths list as a complete root-to-leaf path.

  7. Recursive Exploration: If the current node is not a leaf, recursively call the function on both the left and right children of the current node, if they exist. Before making the recursive call, add "->" to the path string to indicate the path's continuation.

  8. Return Paths: After all recursive calls complete, return the paths list containing all root-to-leaf paths found.

Algorithm Walkthrough

Image
  1. Start at Root (5): The path starts with "5".

  2. Move to Left Child (3): The path updates to "5->3". Since 3 is not a leaf, continue down.

  3. Explore Left of 3 (2): Path updates to "5->3->2". 2 is not a leaf; it has a right child.

    • Move to Right of 2 (1): Path is "5->3->2->1". 1 is a leaf, so add "5->3->2->1" to paths.
  4. Backtrack to 3 and Go Right (4): Path from 5 is "5->3". Now update path to "5->3->4". 4 is a leaf, so add "5->3->4" to paths.

  5. Backtrack to 5 and Move to Right Child (6): Now explore the right side of 5. The path is "5->6". Since 6 is a leaf, add "5->6" to paths.

Completed Paths:

  • By following the steps above, the algorithm discovers all paths:
    • "5->3->2->1"
    • "5->3->4"
    • "5->6"

These steps systematically explore each branch of the tree, ensuring that every unique root-to-leaf path is identified and recorded.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity:

  • : Where N is the number of nodes in the binary tree. In the worst case, we visit each node exactly once to either extend the path string or to backtrack.

Space Complexity:

  • : In the worst-case scenario, the space complexity is determined by the height of the binary tree, which influences the recursion stack depth. For a skewed binary tree (one where every parent node has only one child), the height of the tree can be N, leading to a space complexity of .
Binary Tree Paths (easy)
Find the Difference of Two Arrays (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity:

Space Complexity: